class Solution {
    // void getOneZeroNum(string &str, int &zero, int &one)
    // {
    //     for(auto &ch : str)
    //     {
    //         if(ch == '0') zero++;
    //         else one++;
    //     }
    // }
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        // dp[i][j][k] 表示在前i个数中，选出不超过j，且不超过k的最长子集个数
        int len = strs.size();


        // 下面进行滚动数组优化
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));

        for(int i = 1; i <= len; i++)
        {
            // 统计字符0和字符1的个数
            int zero = 0, one = 0;
            for(auto &ch : strs[i - 1])
            {
                if(ch == '0') zero++;
                else one++;
            }
            for(int j = m; j >= zero; j--)
                for(int k = n; k >= one; k--)
                    dp[j][k] = max(dp[j][k], dp[j - zero][k - one] + 1);
        }
        return dp[m][n];

        // vector<vector<vector<int>>> dp(len + 1, vector<vector<int>>(m + 1, vector<int>(n + 1)));

        // // 初始化第一行dp[0][j][k]，前0个数中选，最长子集的个数就是0
        // for(int i = 1; i <= len; i++)
        // {
        //     for(int j = 0; j <= m; j++)
        //     {
        //         for(int k = 0; k <= n; k++)
        //         {
        //             dp[i][j][k] = dp[i - 1][j][k];
        //             int zero = 0, one = 0;
        //             getOneZeroNum(strs[i - 1], zero, one);
        //             if(j >= zero && k >= one)
        //                 dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - zero][k - one] + 1);
        //         }
        //     }
        // }
        // return dp[len][m][n];
    }
};